/*
 * @lc app=leetcode.cn id=130 lang=cpp
 *
 * [130] 被围绕的区域
 *
 * https://leetcode.cn/problems/surrounded-regions/description/
 *
 * algorithms
 * Medium (46.35%)
 * Likes:    1089
 * Dislikes: 0
 * Total Accepted:    262.9K
 * Total Submissions: 566.6K
 * Testcase Example:  '[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]'
 *
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X'
 * 填充。
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：board =
 * [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
 * 输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
 * 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O'
 * 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：board = [["X"]]
 * 输出：[["X"]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * m == board.length
 * n == board[i].length
 * 1 
 * board[i][j] 为 'X' 或 'O'
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    void DFS(vector<vector<char>>& board, vector<vector<bool>>& isVisited, 
        int r, int c) {
        if ((r < 0 || r >= board.size()) || 
            (c < 0 || c >= board[0].size()) || board[r][c] != 'O' || isVisited[r][c])
            return;

        isVisited[r][c] = true;
        board[r][c] = 'A';
        DFS(board, isVisited, r + 1, c);
        DFS(board, isVisited, r, c + 1);
        DFS(board, isVisited, r - 1, c);
        DFS(board, isVisited, r, c - 1);
    }

    void solve(vector<vector<char>>& board) {
        //类似 1020.飞地的数量, 这里使用一个简单版本
        vector<vector<bool>> isVisited(board.size(), vector<bool>(board[0].size(), false));

        //1.先将边缘进行深度搜索, 将其标记为 'A'
        for (int i = 0, l = 0, r = board[0].size() - 1; i < board.size(); i++) {
            DFS(board, isVisited, i, l);
            DFS(board, isVisited, i, r);
        }
        for (int c = 0, u = 0, d = board.size() - 1; c < board[0].size(); c++) {
            DFS(board, isVisited, u, c);
            DFS(board, isVisited, d, c);
        }

        //2.然后将其进行填充, 'O'->'X', 'A' -> 'O'
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == 'O')
                    board[i][j] = 'X';

                else if (board[i][j] == 'A')
                    board[i][j] = 'O';
            }
        }
    }
};
// @lc code=end

